CMU 15-213 Intro to Computer Systems Lecture 6

课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料：https://github.com/EugeneLiu/translationCSAPP

课程视频：https://www.bilibili.com/video/av31289365/

这一讲介绍了机器级编程2：控制。

控制：条件码

条件码（隐式设置）

单比特寄存器
- CF：进位标志（无符号）
- SF：符号标志（有符号）
- ZF：零标记
- OF：溢出标志（有符号）
通过算术运算隐式设置
- 例如：addq Src, Dest $ \leftrightarrow t = a + b $
- 如果最高有效位进位，则CF置为1（无符号溢出）
- 如果$ t == 0 $，则ZF置为1
- 如果$ t <0 $，则SF置为1
- 如果
  $(a>0 \quad \& \& \quad b>0 \quad \delta \& \quad t<0) \quad|| \quad(a<0 \quad \& \& \quad b<0 \quad \delta \& \quad t>=0)$
  则OF置为1
leaq指令不会改变条件码

条件码（显式设置）

通过比较指令进行显式设置
- cmpq Src2，Src1
- cmpq b，类似于计算a-b而不设置
- 如果最高有效位进位，则CF置为1（无符号溢出）
- 如果$ a == b $，则ZF置为1
- 如果$ (a-b) <0 $，则SF置为1
- 如果
  $(a>0 \quad \& \& \quad b<0 \quad \& \& \quad(a-b)<0) \quad|| \quad(a<0 \quad \& \& \quad b>0 \quad \& \& \quad(a-b)>0)$
  则OF置为1
通过测试指令进行显式设置
- testq Src2，Src1
  - testq b，a类似于计算$a \& b$而不设置dest
- 根据$ \operatorname {Src} 1\& \operatorname {Src} 2 $的值设置条件码
- 使一个操作数成为掩码很有用
- 当$ a \& b == 0 $时设置ZF为1
- 当$a \& b <0 $时设置SF为1

完整比较测试指令如下：

读取条件码

SetX指令
- 根据条件码的组合，将dest的低位字节设置为0或1
- 不会更改剩余的7个字节

来看一个具体例子：

int gt (long x, long y)
{
	return x > y;
}

汇编代码为

cmpq %rsi, %rdi 	# Compare x:y
setg %al 		    # Set when >
movzbl %al, %eax     # Zero rest of %rax
ret

变量和寄存器的对应关系为

条件分支

跳转指令

条件分支例子

考虑如下例子：

long absdiff(long x, long y)
{
    long result;
    if (x > y)
    	result = x-y;
    else
    	result = y-x;
    return result;
}

为了和汇编码格风格相近，首先将上述代码改写为goto的格式：

long absdiff_j(long x, long y)
{
    long result;
    int ntest = x <= y;
    if (ntest) goto Else;
    result = x-y;
    goto Done;
 Else:
    result = y-x;
 Done:
    return result;
}

汇编码为

absdiff: 
    cmpq %rsi, %rdi # x:y
    jle .L4
    movq %rdi, %rax
    subq %rsi, %rax
    ret
.L4: # x <= y
    movq %rsi, %rax
    subq
    ret

变量和寄存器的对应关系为

一般情形如下：

C语言：

val = Test ? Then_Expr : Else_Expr;

汇编码：

    ntest = !Test; 
    if (ntest) goto Else;
    val = Then_Expr;
    goto Done;
Else: 
	val = Else_Expr;
Done:
	. . .

使用条件移动

条件移动指令
- 指令支持：
  - $\text{if (Test) Dest}\leftarrow \text{Src}$
- 在1995年后的x86处理器中受支持
- GCC尝试使用它们
  - 但是，只有在已知安全的情况下为
为什么？
- 分支对流水线中的指令流造成很大破坏
- 条件移动不需要控制转移

C代码

val = Test ? Then_Expr : Else_Expr;

汇编代码

result = Then_Expr;
eval = Else_Expr;
nt = !Test;
if (nt) result = eval;
return result;

一个具体例子如下：

long absdiff(long x, long y)
{
    long result;
    if (x > y)
    	result = x-y;
    else
    	result = y-x;
    return result;
}

汇编码如下：

absdiff:
    movq %rdi, %rax 	# x
    subq %rsi, %rax 	# result = x-y
    movq %rsi, %rdx
    subq %rdi, %rdx 	# eval = y-x
    cmpq %rsi, %rdi 	# x:y
    cmovle %rdx, %rax 	# if <=, result = eval
    ret

寄存器和变量的对应关系如下：

条件移动的坏案例

昂贵的计算
```
val = Test(x) ? Hard1(x) : Hard2(x);
```
- 计算两个值
- 仅在计算非常简单时才有意义
风险计算
```
val = p ? *p : 0;
```
- 计算两个值
- 可能会有不良影响
计算有副作用
```
val = x > 0 ? x*=7 : x+=3;
```
- 计算两个值
- 必须无副作用

循环

“Do-While”循环例子

C代码

long pcount_do(unsigned long x) 
{
    long result = 0;
    do {
        result += x & 0x1;
        x >>= 1;
    } while (x);
    return result;
}

goto版本

long pcount_goto(unsigned long x) 
{
    long result = 0;
  loop:
    result += x & 0x1;
    x >>= 1;
    if(x) goto loop;
    return result;
}

汇编代码

	movl $0, %eax 		# result = 0
.L2: 				    # loop:
    movq %rdi, %rdx
    andl $1, %edx 		 # t = x & 0x1
    addq %rdx, %rax 	 # result += t
    shrq %rdi 			 # x >>= 1
    jne .L2 			# if (x) goto loop
    rep; ret

寄存器和变量的对应关系如下：

一般的”Do-While”翻译

Do-While代码

do
    Body
    while (Test);

Goto版本

loop:
    Body
    if (Test)
    	goto loop

其中Body的形式如下

{ Statement1; Statement2; … Statementn; }

一般的”While”翻译

While代码

while (Test)
	Body

Goto版本

	goto test;
loop:
	Body
test:
    if (Test)
    	goto loop;
done:

另一种方法是将While修改为Do-While

if (!Test)
	goto done;
do
    Body
    while(Test);
done:

Goto版本

if (!Test)
	goto done;
loop:
	Body
	if (Test)
		goto loop;
done:

一般的”For”循环翻译

For循环形式

for (Init; Test; Update )
	Body

修改为While循环

Init;
while (Test) {
    Body
    Update;
}

Switch语句

跳转表结构

Switch分支使用了跳转表结构：

跳转表将分支的条件转换为0到n，然后补齐中间缺失的部分。

例子

C代码

long switch_eg (long x, long y, long z)
{ long w = 1;
    switch(x) { 
    case 1:				//.L3
        w = y*z;
        break; 
    case 2:				//.L5
        w = y/z;
        /* Fall Through */ 
    case 3:				//.L9
    	w += z; 
    	break;
    case 5:				
    case 6: 			//.L7
    	w -= z;
    	break; 
    default:			//.L8
    	w = 2;
    } 
    return w;
}

跳转表

.section .rodata
	.align 8
.L4:
    .quad .L8 # x = 0
    .quad .L3 # x = 1
    .quad .L5 # x = 2
    .quad .L9 # x = 3
    .quad .L8 # x = 4
    .quad .L7 # x = 5
    .quad .L7 # x = 6

总结

C控制
- if-then-else
- do-while
- while, for
- switch
汇编程序控制
- 条件跳跃
- 条件移动
- 间接跳转（通过跳转表）
- 编译器生成代码序列以实现更复杂的控制
标准技术
- 循环转换为do-‐while或jump-to-middle的形式
- 大型switch语句使用跳转表
- 稀疏的switch语句可能使用决策树（if-elseif-elseif-else）